package ch2.link.single;

/**
 * 例2.11：有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法查找L中最大值结点的个数。
 */
public class Exam2_11 {
    public static int Maxcount(LinkListClass<Integer> L) {  //例2.11的算法
        int cnt = 1;  // cnt：统计最大值的个数
        Integer maxe;
        LinkNode<Integer> p = L.head.next;  // p指向首结点
        maxe = p.data;                      // maxe置为首结点值
        while (p.next != null) {            // 循环到p结点为尾结点
            if (p.next.data > maxe) {       // 找到更大的结点
                maxe = p.next.data;
                cnt = 1;
            } else if (p.next.data == maxe) {    // p结点为当前最大值结点
                cnt++;
            }
            p = p.next;
        }
        return cnt;
    }
    public static int MaxCount2(LinkListClass<Integer> L) {
        int cnt = 0;
        LinkNode<Integer> p = L.head.next;
        Integer max = p.data;
        // 1. 找到最大值
        while(p.next != null) {
            if (p.next.data > max) {
                max = p.next.data;
            }
            p = p.next;
        }
        // 2. 统计最大值的个数
        p = L.head.next;
        while(p.next != null) {
            if (p.data == max) {
                cnt++;
            }
            p = p.next;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 5, 3, 5, 5};
        LinkListClass<Integer> L = new LinkListClass<>();
        L.CreateListR(a);
        System.out.println("L: " + L);
        System.out.println("最大值结点个数= " + Exam2_11.Maxcount(L));
        System.out.println("最大值结点个数= " + Exam2_11.MaxCount2(L));
    }
}

